오늘은 글을 조금 일찍 쓰기 시작했다. 생각보다 날짜 문제가 빠르게 해결되어서 까먹기전에 기록을 해두기 위해서이다. 어제 언급했던 날짜 밀림 현상은 각 markdown 파일의 메타데이터 부분의 date 부분에 ‘+0900’을 더해주니까 해결되었다. Google에 ‘jekyll post date’라고 검색하려고 하니 연관검색어로 ‘jekyll post has a future date’를 발견했고, 들어간 뒤 어느 티스토리 블로그1에서 해결방법을 발견할 수 있었다. 역시 티스토리는 최고다.
그리고 마크다운 문법 막상 써보니 엄청 어려운 것 같지는 않다. 중요한 거 몇개는 차근차근 외우고 그때그때 필요한 것만 검색해서 써도 괜찮을 것 같다. 이걸 문제의 해결이라고 볼 수 있는지는 모르겠지만, 마크다운 문법 건은 생각보다 심각한 문제가 아니었기 때문에 언급해둔다.
(+ 2023-06-23 17시 30분에 추가함)
원래는 4시 반쯤에 글 작성을 마무리했는데, 블로그 글 편집기로 사용하는 Visual Studio Code에서 Markdown 파일에 $\LaTeX$ 문법을 이용해서 글을 작성해도 잘 적용이 되어서 별 생각없이 작성을 마치고 나니 로컬 환경에서조차 문법이 전부 깨지는 처참한 사태가 발생했다.
수식을 입력해야 할 상황이 자주 있을 것 같아 언젠가는 끝내야 할 작업이라고 생각하고 열심히 구글링해봤다. 버전이 계속 달라진 탓인지 제대로 작동하지 않는 경우도 많았고, 인라인 기능을 제대로 지원하지 않는 경우도 있는 것 같아 원하는 결과물을 만들어 낼 수 있는 방법을 찾는데 어려움을 겪었다. 결국 어떤 블로그2 덕분에 제대로 작동하는 방법을 발견했다.
급한 불은 껐지만, 아직 남아있는 문제들이 있다.
어쩌면 블로그를 만들고 운영하는 이 자체도 하나의 개인 프로젝트로 봐야될지도 모르겠다. 사실 이제까지는 블로그를 ‘프로젝트’로 취급할 생각은 없었지만, 다른 과제 못지 않은 난이도나 고통이 있는 것 같다…
블로그에 대한 이야기는 이정도로 마무리하고 드디어 B-Tree에 대해 설명을 하도록 하겠다. 오늘은 간단하게 B-Tree의 정의에 대해서 이야기 하도록 하겠다. Wikipedia3를 기준으로 설명하겠다.
B-tree는 ‘Self-balancing tree’의 한 종류이다. Self-balancing tree는 트리 내부의 데이터들이 정렬된 상태를 유지하게 하고, 검색, 순차 접근, 삽입, 그리고 삭제를 $O(\log\ n)$의 시간복잡도 안에 수행할 수 있는 데이터 구조인데, B-tree는 Binary Search Tree를 일반화한 형태의 데이터 구조로, 하나의 노드가 2개 이상의 자식 노드를 가지는 것을 허용한다.
데이터구조에 대해 익숙하지 않은 사람이라면, 설명을 읽어봐도 이해가 안될 것이다. 내가 설명을 제대로 못한 이유도 있지만 노드, 트리, 시간복잡도 등의 개념에 대해 모르기 때문일 수 있다. 모르는 내용의 키워드가 있을 때는 키워드들에 대한 설명을 읽고 오는 것을 권장한다. Wikipedia, 나무위키, 다른 블로그 등 개념들을 친절하고 정확하며 자세하게 설명해둔 자료들이 많이 있을 것이다. 이 글에서 관련 내용들을 모두 다룰 수도 있겠지만, 그렇게 했다가는 하루종일 블로그 글만 써야 할 것이고, 글의 내용이 너무 길어져 가독성을 떨어뜨리게 될 것 같다.
도널드 커누스4의 정의에 따르면, 차수가 $m$인 B-Tree는 아래의 5가지의 성질을 만족한다.
각 성질들에 대해서 아래에서 자세히 설명하도록 하겠다.
이는 B-Tree에 대한 order가 최대 자식 노드의 개수를 의미한다고 생각하면 될 것 같다. 5번의 성질과 엮어서 생각하면, 모든 노드는 최대 $m-1$개의 키를 가질 수 있다는 특징을 이끌어 낼 수 있다.
여기서 $⌈k⌉$는 $k$ 이상의 정수를 나타내는 Ceil 함수로, $⌈m/2⌉$는 B-Tree의 order를 2로 나눈 값을 반올림한 수이다. 이 성질의 의미하는 것은 그 반올림 된 수가 모든 내부 노드가 가져야 하는 최소한의 자식 노드의 개수임을 의미한다.
예를 들어, 어떤 B-Tree의 order가 $5$라고 하면, 모든 내부 노드는 $⌈5/2⌉=3$개 이상의 자식 노드를 가져야 할 것이다. order가 $6$인 경우에도, $⌈6/2⌉=3$개 이상의 자식 노드를 가져야 할 것이다.
이 성질은 2번 성질과 엮어서 생각했을 때, 루트 노드의 자식 수에 대한 제약 조건이라고 생각할 수 있다. 노드들은 루트 노드, 내부 노드, 리프 노드 3가지로 분류할 수 있는데, 리프노드가 아닌 노드는 루트 노드와 내부 노드가 있고, order가 $3$ 이상인 경우 2번 성질을 만족하게 되면 3번 성질은 자동으로 만족하게 된다.
order가 $2$ 이하인 경우라면 이야기가 조금 달라지긴 하는데, $2$ 이하의 order를 가지는 B-Tree도 있는지는 잘 모르겠다. 이 부분은 내 추측인데, $2$ 이하의 order를 가지는 B-Tree는 조금 특이한 형태의 Binary Search Tree로 볼 수 있지 않을까? 5번 성질을 살펴보면 만약 order가 $2$ 이하이면 키 개수가 1개를 초과할 수 없기 때문에 그렇게 생각했다.
루트 노드의 경우는 2번 성질과는 관련이 없기 때문에, 최소한 2개의 자식 노드를 가져야 한다는 조건이 여기서 발생하는 것을 볼 수 있다. 예외적으로 루트 노드가 자식의 개수가 없는 경우도 있을 수 있는데, 이는 루트 노드가 곧 리프 노드인 경우에 ‘리프노드가 아닌 노드’가 아니기 때문에 해당 조건에 영향을 받지 않을 수 있는 것이다.
이 성질에서 말하는 내용은, 어떤 리프 노드에서도 루트 노드부터의 거리가 모두 동일해야 한다는 것으로 생각할 수 있다. 이 조건은 B-Tree에서 중요한 조건이라고 할 수 있는데, B-Tree가 다양한 연산을 $O(\log\ n)$의 시간복잡도로 수행할 수 있게 해주는 조건이기 때문이다.
이 성질에서 말하는 것은 말 그대로 리프노드가 아닌 노드들은 자식 노드의 개수보다 하나 적은 개수의 키를 가져야 한다는 것이다. B-Tree에서 요소를 찾는 과정을 생각해보면, 더도 덜도 말고 딱 한 개가 더 적어야 한다는 사실을 알 수 있다.
B-Tree에 대한 설명은 여기서 마무리하겠다. 원문의 내용을 빠짐없이 전달하면서 내가 생각한 내용들을 정리해보았다. 이제 내일부터는 이런 성질을 만족하는 B-Tree에서 다양한 연산을 수행하는 방법들에 대하여 정리해보고, B-Tree의 설명이 마무리되는 대로 프로젝트 진척상황을 정리할 것이다.
이대로 B-Tree 설명만 늘어놓고 끝내기에는 뭔가 아쉬우니 잡담이나 잠깐 적어보겠다.
오늘 점심밥을 먹고 아이스 아메리카노를 먹다가 든 생각이다. 커피샵에서 커피를 주문 할 때 아이스 아메리카노를 주문하면, 커피가 나올 때, 얼음이 들어있는 아메리카노가 나오게 된다. 만약 어떤 진상 손님이 커피를 받아간 뒤 마시지 않고 얼음이 다 녹을 때까지 기다린 뒤, 아이스 아메리카노 인데 얼음이 들어있지 않다고 우기면 어떨까? 영업방해일 뿐일 것이다. 아이스 아메리카노를 주문하면 ‘서빙이 되는 시점’에 ‘아이스 아메리카노’인 물체가 나오게 되는 것이다. 그렇다면, 뜨거운 아이스 아메리카노도 가능하지 않을까?
예를 들어 커피를 만들 때 물의 온도를 $99^\circ C$로 맞춰두고, 얼음을 넣자마자 서빙을 한다면, 적어도 서빙을 하는 순간에는 ‘뜨거운 아이스 아메리카노’ 아닐까? 그렇다면 뜨거운 아이스 아메리카노를 주문하는 것도 가능한 것이다. 그 커피를 받고 난 후에 얼음이 다 녹아버리거나 미지근해지는 건 괜찮다. ‘서빙하는 시점’에만 ‘뜨거운 아이스 아메리카노’면 되기 때문이다.
라는 웃긴 생각이 문득 들었다. 진지하게 쓴 글은 아니니 웃고 넘어가주면 좋겠다.
지난 번에 ‘분반 친구’라는 키워드를 사용하면서 주석에다가 분반 제도에 대해서 나중에 설명해겠다고 적어 놓은걸 봤다. 까먹기 전에 빨리 이야기 해둬야 겠다. 내가 지금 다니고 있는 대학교는 1학년 1학기 부터 2학년 1학기까지 ‘무은재학부’라는 학부에 소속되게 된다. 3학기 동안은 과가 없는 상태인 것이다. 대신 신입생 약 300명을 각 분반 당 약 20명 정도씩 나누어 총 15개의 분반을 만들어준다. 그리고 1학년 1학기 동안 같은 분반 친구끼리 다니면서 친분을 쌓게 된다. 나는 12분반이고, 언급했던 분반 친구는 같은 학과를 지망중인 어떤 12분반 친구인 것이다. 듣는 수업도 비슷해서 자주 같이 다녔고, 그러다 보니 과제에 대한 이야기도 하게 된 것이다. 분반에 대한 설명은 여기서 마치겠다. 폭풍십이 화이팅!
잡담을 써보니 되게 재밌다. 원래 오늘 잡담 내용은 2개로 마치려고 했는데, 이 내용까지만 더 쓰고 마무리 해야겠다. 중요한 이야기는 아니고, 앞으로 이렇게 포스트에 잡담을 자주 쓰게 될 것 같다는 내용이다. 그날그날 있었던 재미있는 에피소드라던가, 오늘 점심 먹으면서 생각난 헛소리라던가, 아니면 학교 생활 같은 내용도 괜찮을 것 같고, 혹은 간간히 드는 고민 같은 걸 적게 될지도 모르겠다. 물론 잡담을 적는다고 해서 블로그의 본 목적인 개발 내용 정리를 소홀히 하지는 않을 것이다. 그래도 너무 그런 내용만 적으면 딱딱하기도 하고, 기왕 하는거 나도 재밌게 하려면 이런 걸 넣으면서 진행하는게 좋을 것 같다.
오늘은 이 정도로 글을 마무리 하려고 한다. 내일부터는 B-Tree에서 지원하는 다양한 기능들에 대해서 이야기 해보도록 하겠다. 원래는 밤까지 코딩하고 그 후에 블로그 글을 쓰는 식이었는데, 일찍 블로그 글을 쓰기 시작하니 시간에 안 쫓기고 좋은 것 같다. 대신 하루 계획이 와장창 무너지는 것 같으니, 빨리빨리 쓰는 습관을 들여야 할 것 같다.
오늘의 개발은 여기까지!
1: https://hurderella.tistory.com/128
2: https://ionathan.ch/2021/05/19/latex-in-jekyll.html
3: https://en.wikipedia.org/wiki/B-tree
4: https://en.wikipedia.org/wiki/Donald_Knuth